#include <assert.h>
#include <iostream>
#include <list>
#include <vector>

#include "test.h"
#include "FibonacciHeap.h"

using namespace std;

void test1()
{
	FibonacciHeap<size_t> heap;
	cout << "heap.verify()=" << heap.verify() << endl;
	heap.show(std::cout, 1) << endl;
	heap.insert(100);
	cout << "heap.insert(100)" << endl;
	heap.show(std::cout, 1) << endl;
	cout << "heap.verify()=" << heap.verify() << endl;
}

void test2()
{
	FibonacciHeap<size_t> h11, h12;
	cout << "h11.verify()=" << h11.verify() << endl;
	h11.show(std::cout << "h11:", 1) << endl;
	cout << "h12.verify()=" << h12.verify() << endl;
	h12.show(std::cout << "h12:", 1) << endl;
	cout << "h11.merge(h12);" << endl;
	h11.merge(h12);
	cout << "h11.verify()=" << h11.verify() << endl;
	h11.show(std::cout << "h11:", 1) << endl;
	cout << "h12.verify()=" << h12.verify() << endl;
	h12.show(std::cout << "h12:", 1) << endl;

	cout << string(20, '-') << endl;
	FibonacciHeap<size_t> h21, h22;
	h21.insert(100);
	cout << "h21.insert(100)" << endl;
	cout << "h21.verify()=" << h21.verify() << endl;
	h21.show(std::cout << "h21:", 1) << endl;
	cout << "h22.verify()=" << h22.verify() << endl;
	h22.show(std::cout << "h22:", 1) << endl;
	cout << "h21.merge(h22);" << endl;
	h21.merge(h22);
	cout << "h21.verify()=" << h21.verify() << endl;
	h21.show(std::cout << "h21:", 1) << endl;
	cout << "h22.verify()=" << h22.verify() << endl;
	h22.show(std::cout << "h22:", 1) << endl;

	cout << string(20, '-') << endl;
	FibonacciHeap<size_t> h31, h32;
	h32.insert(100);
	cout << "h32.insert(100)" << endl;
	cout << "h31.verify()=" << h31.verify() << endl;
	h31.show(std::cout << "h31:", 1) << endl;
	cout << "h32.verify()=" << h32.verify() << endl;
	h32.show(std::cout << "h32:", 1) << endl;
	cout << "h31.merge(h32);" << endl;
	h31.merge(h32);
	cout << "h31.verify()=" << h31.verify() << endl;
	h31.show(std::cout << "h31:", 1) << endl;
	cout << "h32.verify()=" << h32.verify() << endl;
	h32.show(std::cout << "h32:", 1) << endl;

	cout << string(20, '-') << endl;
	FibonacciHeap<size_t> h41, h42;
	h41.insert(100);
	cout << "h41.insert(100)" << endl;
	h42.insert(200);
	cout << "h42.insert(200)" << endl;
	cout << "h41.verify()=" << h41.verify() << endl;
	h41.show(std::cout << "h41:", 1) << endl;
	cout << "h42.verify()=" << h42.verify() << endl;
	h42.show(std::cout << "h42:", 1) << endl;
	cout << "h41.merge(h42);" << endl;
	h41.merge(h42);
	cout << "h41.verify()=" << h41.verify() << endl;
	h41.show(std::cout << "h41:", 1) << endl;
	cout << "h42.verify()=" << h42.verify() << endl;
	h42.show(std::cout << "h42:", 1) << endl;

	cout << string(20, '-') << endl;
	FibonacciHeap<size_t> h51, h52;
	h51.insert(200);
	cout << "h51.insert(200)" << endl;
	h52.insert(100);
	cout << "h52.insert(100)" << endl;
	cout << "h51.verify()=" << h51.verify() << endl;
	h51.show(std::cout << "h51:", 1) << endl;
	cout << "h52.verify()=" << h52.verify() << endl;
	h52.show(std::cout << "h52:", 1) << endl;
	cout << "h51.merge(h52);" << endl;
	h51.merge(h52);
	cout << "h51.verify()=" << h51.verify() << endl;
	h51.show(std::cout << "h51:", 1) << endl;
	cout << "h52.verify()=" << h52.verify() << endl;
	h52.show(std::cout << "h52:", 1) << endl;

}

void test3()
{
	FibonacciHeap<size_t> h;
	h.insert(200);
	h.insert(100);
	h.insert(300);
	cout << "h.verify()=" << h.verify() << ",";
	h.show(std::cout, 1) << endl;

	cout << "auto pNode = h.extractMin();" << endl;
	auto pNode = h.extractMin();
	cout << "h.verify()=" << h.verify() << ",";
	h.show(std::cout, 1) << endl;
	cout << "pNode=" << (*pNode)->_k << endl;
	cout << "h.insert(100)" << endl;
	h.insert(pNode);
	cout << "h.verify()=" << h.verify() << ",";
	h.show(std::cout, 1) << endl;
}

void test4()
{
	FibonacciHeap<size_t> h, tmpH;
	{
		tmpH.insert(1);
		tmpH.insert(24);
		tmpH.insert(46);
		tmpH.insert(26);
		tmpH.insert(35);
		auto pNode = tmpH.extractMin();
		h.merge(tmpH);
		tmpH.insert(pNode);
		tmpH.insert(17);
		tmpH.insert(30);
		pNode = tmpH.extractMin();
		h.merge(tmpH);
		tmpH.insert(pNode);
		tmpH.insert(18);
		tmpH.insert(19);
		tmpH.insert(39);
		tmpH.insert(50);
		tmpH.insert(3);
		tmpH.insert(52);
		tmpH.insert(38);
		tmpH.insert(41);
		pNode = tmpH.extractMin();
		{

			cout << "tmpH.verify()=" << tmpH.verify() << ",";
			tmpH.show(std::cout, 1) << endl;
#if 0
			auto pTmpNodePtr = tmpH.erase(19);
			delete(*pTmpNodePtr);
			pTmpNodePtr.reset();
#endif
			auto pTmpNode = tmpH.find(19);
			tmpH.decreaseKey(pTmpNode, 1);
			auto pTmpNodePtr = tmpH.extractMin();
			delete(*pTmpNodePtr);
			pTmpNodePtr.reset();

			cout << "tmpH.verify()=" << tmpH.verify() << ",";
			tmpH.show(std::cout, 1) << endl;


			pTmpNode = tmpH.find(50);
			tmpH.decreaseKey(pTmpNode, 1);
			pTmpNodePtr = tmpH.extractMin();
			delete(*pTmpNodePtr);
			pTmpNodePtr.reset();
		}
		cout << "tmpH.verify()=" << tmpH.verify() << ",";
		tmpH.show(std::cout, 1) << endl;
		h.merge(tmpH);
		cout << "h.verify()=" << h.verify() << ",";
		h.show(std::cout, 1) << endl;
		h.insert(23);
		h.insert(7);
		h.insert(21);
		cout << "h.verify()=" << h.verify() << ",";
		h.show(std::cout, 1) << endl;
		delete(*pNode);
		pNode.reset();
		pNode = h.extractMin();
		cout << "h.verify()=" << h.verify() << ",";
		h.show(std::cout, 1) << endl;
	}

}